package main

import "fmt"

/*
 	超级次方
你的任务是计算 ab 对 1337 取模，a 是一个正整数，b 是一个非常大的正整数且会以数组形式给出。


示例 1：
输入：a = 2, b = [3]
输出：8

示例 2：
输入：a = 2, b = [1,0]
输出：1024
 */

// 二进制下的快速幂拓展到十进制下的快速幂
// 参考文章 https://zhuanlan.zhihu.com/p/95902286
func superPow(a int, b []int) int {
	mod := 1337
	tag := a % mod
	res := 1

	for i := len(b) - 1; i >= 0; i-- {
		dec := b[i]
		if dec != 0 {
			res = (res * pow(tag, dec, mod)) % mod
		}
		tag = pow(tag, 10, mod)
	}
	return res
}

// 计算 (a^n)%mod
func pow(a int, n int, mod int) int {
	tag := a % mod
	res := 1

	for n != 0 {
		if n&1 != 0 {
			res = (res * tag) % mod
		}
		tag = (tag * tag) % mod
		n >>= 1
	}

	return res
}

func main() {
	res := superPow(2, []int{1,5})
	fmt.Println(res)
}
